package leetcode.primary;

public class T152 {
    public int maxProduct(int[] nums) {
        Tuple[] dp = new Tuple[nums.length];
        dp[0] = new Tuple();
        int max = nums[0];
        if (nums[0]>=0){
            dp[0].PMax = nums[0];
        }else {
            dp[0].NMax = nums[0];
        }
        for (int i = 1; i < nums.length; i++) {
            Tuple tuple = new Tuple();
            if (nums[i]>0){
                tuple.PMax = Math.max(nums[i]*dp[i-1].PMax,nums[i]);
                tuple.NMax = nums[i]*dp[i-1].NMax;
            }else {
                tuple.NMax = Math.min(nums[i]*dp[i-1].PMax,nums[i]);
                tuple.PMax = nums[i]*dp[i-1].NMax;
            }
            if (tuple.PMax>max){
                max = tuple.PMax;
            }
            dp[i] = tuple;
        }

        System.out.print("最小值：");
        for (int i = 0; i < dp.length; i++) {
            System.out.print(dp[i].NMax+" ");
        }
        System.out.println();

        System.out.print("最大值：");
        for (int i = 0; i < dp.length; i++) {
            System.out.print(dp[i].PMax+" ");
        }
        System.out.println();
        return max;

    }

    public static void main(String[] args) {
        T152 t152 = new T152();
        int product = t152.maxProduct(new int[]{-2,3,-4});
        System.out.println(product);
    }
}

class Tuple{
    int NMax=0;  //负的最大值
    int PMax=0;   //正的最大值
}